# 接雨水：力扣上还有我写的暴力解法，这里只写栈解决

height = [0,1,0,2,1,0,1,3,2,1,2,1]

class Solution:
    """ 调用递减栈实现 """
    def trap(self, height):
        stack = list()
        sums = 0
        i = 0
        while i < len(height):
            while stack != [] and height[i] > height[stack[-1]]:
                a = stack.pop()
                # 当去除栈中最后一个元素的时候，如果栈空了，那形不成低洼，接不到雨水，直接退出
                if stack == []:
                    break                   
                # 计算低洼的宽
                width = i - stack[-1] - 1
                # 高
                high = min(height[stack[-1]], height[i]) - height[a]
                # 计算盛水面积
                area = width * high
                # 面积累加
                sums += area
            
            stack.append(i)
            i += 1
        return sums

s = Solution()
sums = s.trap(height)
print(sums)



"""
然后看这个数（数组排序后）每位相加 除 3 余几。
情况1：  余数  0， 直接返回该数组
情况2： 余数为 n， 查找 数组中是否有 这个数， 有的话删除掉， 返回数组
情况3： （分析不透的点），当没有 数 为 carry 时， 使 n + 3, 若在 数组中删除掉也行，
        或者一直迭代 n + 3 + 3
        4.  直到 n 大于 10. 那么变成两数之和了， 在有序数组中找 和 为 n 的 数。 删除掉这俩数
        5. 但不能保证 两数相加一定有结果， 所以要进行三数之和加， 可能四数之和。。。以此类推
"""
